<!DOCTYPE html>






  


<html class="theme-next mist use-motion" lang="zh-CN">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2"/>
<meta name="theme-color" content="#222">












<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />






















<link href="/blog/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/blog/css/main.css?v=6.2.0" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/blog/images/apple-touch-icon-next.png?v=6.2.0">


  <link rel="icon" type="image/png" sizes="32x32" href="/blog/images/favicon-32x32-next.png?v=6.2.0">


  <link rel="icon" type="image/png" sizes="16x16" href="/blog/images/favicon-16x16-next.png?v=6.2.0">


  <link rel="mask-icon" href="/blog/images/logo.svg?v=6.2.0" color="#222">









<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/blog/',
    scheme: 'Mist',
    version: '6.2.0',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: false,
    fastclick: false,
    lazyload: false,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>


  




  <meta name="description" content="“我发现我大学里面学过的课程，像数据结构，计算机原理等一些课程。在我现在编码的过程中都非常有用。”——前陆家嘴沈高级开发工程师吹风   排序算法么，又是面初中级工程师的一个问题。面试结尾或者是中场，往往面试官会说写个冒泡，然后自己把好不容易把背下来的、很有可能写错的、字写的很丑的排序算法写下来。面试官可能很不懈的看了眼，然后就没了。可能写个排序算法是对面试者的一个尊重吧。">
<meta name="keywords" content="算法与数据结构">
<meta property="og:type" content="article">
<meta property="og:title" content="第 3 章 排序算法">
<meta property="og:url" content="http://meixl.gitee.io/20180507/第3章_排序算法/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="“我发现我大学里面学过的课程，像数据结构，计算机原理等一些课程。在我现在编码的过程中都非常有用。”——前陆家嘴沈高级开发工程师吹风   排序算法么，又是面初中级工程师的一个问题。面试结尾或者是中场，往往面试官会说写个冒泡，然后自己把好不容易把背下来的、很有可能写错的、字写的很丑的排序算法写下来。面试官可能很不懈的看了眼，然后就没了。可能写个排序算法是对面试者的一个尊重吧。">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="http://meixl.gitee.io/blog/images/pasted-23.png">
<meta property="og:image" content="http://meixl.gitee.io/blog/images/pasted-25.png">
<meta property="og:image" content="http://meixl.gitee.io/blog/images/pasted-24.png">
<meta property="og:image" content="http://meixl.gitee.io/blog/images/pasted-26.png">
<meta property="og:image" content="http://meixl.gitee.io/blog/images/pasted-27.png">
<meta property="og:image" content="http://meixl.gitee.io/blog/images/pasted-30.png">
<meta property="og:updated_time" content="2019-09-02T07:10:55.490Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="第 3 章 排序算法">
<meta name="twitter:description" content="“我发现我大学里面学过的课程，像数据结构，计算机原理等一些课程。在我现在编码的过程中都非常有用。”——前陆家嘴沈高级开发工程师吹风   排序算法么，又是面初中级工程师的一个问题。面试结尾或者是中场，往往面试官会说写个冒泡，然后自己把好不容易把背下来的、很有可能写错的、字写的很丑的排序算法写下来。面试官可能很不懈的看了眼，然后就没了。可能写个排序算法是对面试者的一个尊重吧。">
<meta name="twitter:image" content="http://meixl.gitee.io/blog/images/pasted-23.png">






  <link rel="canonical" href="http://meixl.gitee.io/20180507/第3章_排序算法/"/>



<script type="text/javascript" id="page.configurations">
  CONFIG.page = {
    sidebar: "",
  };
</script>

  <title>第 3 章 排序算法 | Hexo</title>
  









  <noscript>
  <style type="text/css">
    .use-motion .motion-element,
    .use-motion .brand,
    .use-motion .menu-item,
    .sidebar-inner,
    .use-motion .post-block,
    .use-motion .pagination,
    .use-motion .comments,
    .use-motion .post-header,
    .use-motion .post-body,
    .use-motion .collection-title { opacity: initial; }

    .use-motion .logo,
    .use-motion .site-title,
    .use-motion .site-subtitle {
      opacity: initial;
      top: initial;
    }

    .use-motion {
      .logo-line-before i { left: initial; }
      .logo-line-after i { right: initial; }
    }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">

  
  
    
  

  <div class="container sidebar-position-left page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/blog/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">Hexo</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button aria-label="切换导航栏">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>




<nav class="site-nav">
  
    <ul id="menu" class="menu">
      
        
        
        
          
          <li class="menu-item menu-item-home">
    <a href="/blog/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-home"></i> <br />首页</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-tags">
    <a href="/blog/tags" rel="section">
      <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />标签</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-archives">
    <a href="/blog/archives/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />归档</a>
  </li>
        
        
        
          
          <li class="menu-item menu-item-about">
    <a href="/blog/about/" rel="section">
      <i class="menu-item-icon fa fa-fw fa-user"></i> <br />关于</a>
  </li>

      
      
    </ul>
  

  
    

  

  
</nav>



  



</div>
    </header>

    


    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  

  
  
  

  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://meixl.gitee.io/blog/20180507/第3章_排序算法/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="meixiaoliang">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/blog/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Hexo">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">第 3 章 排序算法
              
            
          </h1>
        

        <div class="post-meta">

          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2018-05-07 20:57:00" itemprop="dateCreated datePublished" datetime="2018-05-07T20:57:00+08:00">2018-05-07</time>
            

            
              

              
                
                <span class="post-meta-divider">|</span>
                

                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                
                  <span class="post-meta-item-text">更新于</span>
                
                <time title="修改时间：2019-09-02 15:10:55" itemprop="dateModified" datetime="2019-09-02T15:10:55+08:00">2019-09-02</time>
              
            
          </span>
		  
		  <!-- 字数统计 -->
		  <span class="post-meta-divider">|</span>
		  <span class="post-meta-item-icon">
		    <i class="fa fa-file-word-o"></i>
		  </span>
		  <span class="post-meta-item-text">
		    字数统计 1,418 字
		  </span>

          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        <blockquote>
<p>“我发现我大学里面学过的课程，像数据结构，计算机原理等一些课程。在我现在编码的过程中都非常有用。”——前陆家嘴沈高级开发工程师<del>吹风</del> </p>
</blockquote>
<p>排序算法么，又是面初中级工程师的一个问题。面试结尾或者是中场，往往面试官会说写个冒泡，然后自己把<del>好不容易把背下来的、很有可能写错的、字写的很丑的</del>排序算法写下来。面试官可能很不懈的看了眼，然后就没了。可能写个排序算法是对面试者的一个尊重吧。<br><a id="more"></a></p>
<hr>
<h1 id="算法基础"><a href="#算法基础" class="headerlink" title="算法基础"></a>算法基础</h1><h2 id="时间复杂度"><a href="#时间复杂度" class="headerlink" title="时间复杂度"></a>时间复杂度</h2><p>算法的复杂度的讨论，主要是围绕时间复杂度。空间复杂度次要，现在 1T 的硬盘也就几百块。比如扑克牌 54 张牌，即可以用写个 <code>for</code> 循环生成，也可以用一个数组表示。</p>
<h2 id="空间复杂度"><a href="#空间复杂度" class="headerlink" title="空间复杂度"></a>空间复杂度</h2><h2 id="稳定性"><a href="#稳定性" class="headerlink" title="稳定性"></a>稳定性</h2><p>复杂度在这里才出现</p>
<h1 id="快而简单的排序——桶排序"><a href="#快而简单的排序——桶排序" class="headerlink" title="快而简单的排序——桶排序"></a>快而简单的排序——桶排序</h1><h2 id="介绍"><a href="#介绍" class="headerlink" title="介绍"></a>介绍</h2><p><img src="\blog\images\pasted-23.png" alt="upload successful"></p>
<ol>
<li>建立 N 个桶，N &gt;= 要排序的最大值。</li>
<li>将对象丢到桶里</li>
<li>遍历桶，输出排序结果。  </li>
</ol>
<h2 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h2><p>上 <code>Java</code> 代码：<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">BucketSort</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">		<span class="keyword">int</span>[] array1 = &#123; <span class="number">1</span>, <span class="number">10</span>, <span class="number">20</span>, <span class="number">50</span>, <span class="number">30</span> &#125;;</span><br><span class="line">		<span class="keyword">int</span>[] array2 = <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">51</span>];</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> num : array1) &#123;</span><br><span class="line">			array2[num] = num;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> num : array2) &#123;</span><br><span class="line">			<span class="keyword">if</span> (<span class="number">0</span> != num) &#123;</span><br><span class="line">				System.out.print(num + <span class="string">","</span>);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>结果：<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="number">1</span>,<span class="number">10</span>,<span class="number">20</span>,<span class="number">30</span>,<span class="number">50</span>,</span><br></pre></td></tr></table></figure></p>
<h2 id="性能及特点"><a href="#性能及特点" class="headerlink" title="性能及特点"></a>性能及特点</h2><p>优点：速度快、简单。真的是简单，一下子就记下来了，冒泡排序一直没背下来，应该是没有理解把。今天晚上看完就懂了。<br>缺点：空间利用率低。如果元素分布过散，比如 1,100,10000000。需要建立的桶有点多，调用别的排序，可能 10 次以内就好了。这种情况就不适合桶排序。</p>
<h2 id="时间复杂度-1"><a href="#时间复杂度-1" class="headerlink" title="时间复杂度"></a>时间复杂度</h2><p>O(N+M) N 为待排序元素个数，M 为桶个数。<strong>简单暴力</strong></p>
<h1 id="咕噜咕噜的冒泡排序"><a href="#咕噜咕噜的冒泡排序" class="headerlink" title="咕噜咕噜的冒泡排序"></a>咕噜咕噜的冒泡排序</h1><h2 id="原理"><a href="#原理" class="headerlink" title="原理"></a>原理</h2><ol>
<li>n 个元素进行 n - 1 次排序。</li>
<li>每次将当前元素和它后面的那个元素进行比较，若当前元素大于后面的元素，则交换位置。</li>
<li>一次交换完毕，最后一个元素为最大值。</li>
<li>循环上面的操作，每次排好的元素不需要再次进入排序队列。</li>
</ol>
<h2 id="代码-1"><a href="#代码-1" class="headerlink" title="代码"></a>代码</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">BubbleSort1</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span>[] array = &#123; <span class="number">100</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">5</span>, <span class="number">7</span>, <span class="number">8</span>, <span class="number">10</span>, <span class="number">4</span>, <span class="number">6</span> &#125;;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; array.length; i++) &#123;</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; array.length - <span class="number">1</span> - i; j++) &#123;</span><br><span class="line">                <span class="keyword">if</span> (array[j] &gt; array[j + <span class="number">1</span>]) &#123;</span><br><span class="line">                    <span class="keyword">int</span> temp = array[j];</span><br><span class="line">                    array[j] = array[j + <span class="number">1</span>];</span><br><span class="line">                    array[j + <span class="number">1</span>] = temp;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        System.out.println(Arrays.toString(array));</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>这里交换的 3 行代码，也很好记。先声明临时变量，然后 3 个变量如图每个出现 2 次。<br>这个是我在<code>达内</code>培训时，<code>朱德烈</code>老师教我的。</p>
<p><img src="\blog\images\pasted-25.png" alt="upload successful"></p>
<p>结果：<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">[<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">7</span>, <span class="number">8</span>, <span class="number">10</span>]</span><br></pre></td></tr></table></figure></p>
<h2 id="题外话"><a href="#题外话" class="headerlink" title="题外话"></a>题外话</h2><p><strong>冒泡排序这玩意，初中级的面试很有可能会问到。</strong> 打不上来，就打折扣了。  </p>
<blockquote>
<p>“那为啥我们公司出的冒泡看不懂 ？”——某鹰潭老表  </p>
</blockquote>
<p><img src="\blog\images\pasted-24.png" alt="upload successful"><br>如图所示，其实冒泡排序的写法，是一个 2 * 2 的。构成一个<a href="https://baike.baidu.com/item/%E7%AC%9B%E5%8D%A1%E5%B0%94%E4%B9%98%E7%A7%AF/6323173?fr=aladdin&amp;fromid=1434391&amp;fromtitle=%E7%AC%9B%E5%8D%A1%E5%B0%94%E7%A7%AF" target="_blank" rel="noopener">笛卡尔积</a>。可能自己对冒泡排序并没有很了解，然后又是背的。所以换一下就不认识了。记一个就好，反正面试又不会闲的蛋疼叫你写 4 个。</p>
<h2 id="特点及性能"><a href="#特点及性能" class="headerlink" title="特点及性能"></a>特点及性能</h2><blockquote>
<ul>
<li>时间复杂度<br>O(n2)：最坏的情况，要排序的数组是需要结果的倒序。<br>0(n)：最好的情况，要排序的数组正好是想要的结果。</li>
<li>空间复杂度<br>O(1)：就用于交换的那个临时变量是额外需要的。</li>
</ul>
</blockquote>
<p><img src="\blog\images\pasted-26.png" alt="upload successful"></p>
<h2 id="改进方案"><a href="#改进方案" class="headerlink" title="改进方案"></a>改进方案</h2><p><img src="\blog\images\pasted-27.png" alt="upload successful"><br>第一个我理解为做标记，顺序对的就不用管。可以把别的放到他们之间，或者是这一块可以当做一个泡来排。<br>第二个我理解为一次排 2 个，总排序次数不变，每次排序要遍历的个数 -2 而不是 -1。<br><img src="\blog\images\pasted-30.png" alt="upload successful"></p>
<h1 id="简单的插入排序"><a href="#简单的插入排序" class="headerlink" title="简单的插入排序"></a>简单的插入排序</h1><h2 id="原理-1"><a href="#原理-1" class="headerlink" title="原理"></a>原理</h2><p>插排也是一种简单的排序（理解前提）。</p>
<h2 id="代码-2"><a href="#代码-2" class="headerlink" title="代码"></a>代码</h2><p>上代码，语言表达能力比较欠。<br>这里的排序代码，自己也没有写出来。看了别人的博客才搞懂的<a href="https://www.cnblogs.com/jingmoxukong/p/4303270.htmlf" target="_blank" rel="noopener">排序三 直接插入排序</a>。<br>一方面是原理的理解，另一方面则是代码能力也有点欠。<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 插入排序</span></span><br><span class="line"><span class="comment"> * 从左到右,小的在前，大的在后</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">InsertSort</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span>[] array = &#123; <span class="number">6</span>, <span class="number">3</span>, <span class="number">3</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">3</span>, <span class="number">1</span>, <span class="number">0</span>, <span class="number">6</span>, <span class="number">4</span> &#125;;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; array.length; i++) &#123;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">int</span> temp = array[i];</span><br><span class="line">            <span class="keyword">int</span> j;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">for</span> (j = i - <span class="number">1</span>; j &gt;= <span class="number">0</span> &amp;&amp; array[j] &gt; temp; j--) &#123;</span><br><span class="line">                array[j + <span class="number">1</span>] = array[j];</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line">            array[j + <span class="number">1</span>] = temp;</span><br><span class="line"></span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        System.out.println(Arrays.toString(array));</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>结果：<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">[<span class="number">0</span>, <span class="number">1</span>, <span class="number">3</span>, <span class="number">3</span>, <span class="number">3</span>, <span class="number">4</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">6</span>, <span class="number">6</span>]</span><br></pre></td></tr></table></figure></p>
<p>代码中自己有 2 处是一开始没有想到的:    </p>
<ol>
<li>j 的赋值单独拎出，属性值公用</li>
<li>第 2 个 for 循环中， j &gt;= 0 &amp;&amp; array[j] &gt; temp 的公用，双重判断    </li>
</ol>
<h2 id="特点及性能-1"><a href="#特点及性能-1" class="headerlink" title="特点及性能"></a>特点及性能</h2><p>和<code>冒泡排序</code>一样，<code>插入排序</code>时间复杂度也是 O(n2)。当数组越近似结果有序，排序速度越快<del>废话</del>。<br>空间复杂度也是 O (1)，需要一个额外的空间存储临时变量。</p>
<h1 id="最常用的快速排序"><a href="#最常用的快速排序" class="headerlink" title="最常用的快速排序"></a>最常用的快速排序</h1><h1 id="直接插入的改进——希尔排序"><a href="#直接插入的改进——希尔排序" class="headerlink" title="直接插入的改进——希尔排序"></a>直接插入的改进——希尔排序</h1><h1 id="简单选择排序"><a href="#简单选择排序" class="headerlink" title="简单选择排序"></a>简单选择排序</h1><h1 id="小结"><a href="#小结" class="headerlink" title="小结"></a>小结</h1>
      
    </div>

    

    
    
    

    

    

    

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/blog/tags/算法与数据结构/" rel="tag"># 算法与数据结构</a>
          
        </div>
      

      
      
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/blog/20180506/第2章_栈、队列、链表/" rel="next" title="第 2 章 栈、队列、链表">
                <i class="fa fa-chevron-left"></i> 第 2 章 栈、队列、链表
              </a>
            
          </div>

          <span class="post-nav-divider"></span>

          <div class="post-nav-prev post-nav-item">
            
          </div>
        </div>
      

      
      
    </footer>
  </div>
  
  
  
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          

  



        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview-wrap sidebar-panel">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <p class="site-author-name" itemprop="name">meixiaoliang</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          
            <nav class="site-state motion-element">
              
                <div class="site-state-item site-state-posts">
                
                  <a href="/blog/archives/">
                
                    <span class="site-state-item-count">3</span>
                    <span class="site-state-item-name">日志</span>
                  </a>
                </div>
              

              

              
                
                
                <div class="site-state-item site-state-tags">
                  <a href="/blog/tags/index.html">
                    
                    
                      
                    
                    <span class="site-state-item-count">1</span>
                    <span class="site-state-item-name">标签</span>
                  </a>
                </div>
              
            </nav>
          

          

          

          
          

          
          

          
            
          
          

        </div>
      </section>

      
      <!--noindex-->
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
              
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#算法基础"><span class="nav-number">1.</span> <span class="nav-text">算法基础</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#时间复杂度"><span class="nav-number">1.1.</span> <span class="nav-text">时间复杂度</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#空间复杂度"><span class="nav-number">1.2.</span> <span class="nav-text">空间复杂度</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#稳定性"><span class="nav-number">1.3.</span> <span class="nav-text">稳定性</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#快而简单的排序——桶排序"><span class="nav-number">2.</span> <span class="nav-text">快而简单的排序——桶排序</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#介绍"><span class="nav-number">2.1.</span> <span class="nav-text">介绍</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#代码"><span class="nav-number">2.2.</span> <span class="nav-text">代码</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#性能及特点"><span class="nav-number">2.3.</span> <span class="nav-text">性能及特点</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#时间复杂度-1"><span class="nav-number">2.4.</span> <span class="nav-text">时间复杂度</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#咕噜咕噜的冒泡排序"><span class="nav-number">3.</span> <span class="nav-text">咕噜咕噜的冒泡排序</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#原理"><span class="nav-number">3.1.</span> <span class="nav-text">原理</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#代码-1"><span class="nav-number">3.2.</span> <span class="nav-text">代码</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#题外话"><span class="nav-number">3.3.</span> <span class="nav-text">题外话</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#特点及性能"><span class="nav-number">3.4.</span> <span class="nav-text">特点及性能</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#改进方案"><span class="nav-number">3.5.</span> <span class="nav-text">改进方案</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#简单的插入排序"><span class="nav-number">4.</span> <span class="nav-text">简单的插入排序</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#原理-1"><span class="nav-number">4.1.</span> <span class="nav-text">原理</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#代码-2"><span class="nav-number">4.2.</span> <span class="nav-text">代码</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#特点及性能-1"><span class="nav-number">4.3.</span> <span class="nav-text">特点及性能</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#最常用的快速排序"><span class="nav-number">5.</span> <span class="nav-text">最常用的快速排序</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#直接插入的改进——希尔排序"><span class="nav-number">6.</span> <span class="nav-text">直接插入的改进——希尔排序</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#简单选择排序"><span class="nav-number">7.</span> <span class="nav-text">简单选择排序</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#小结"><span class="nav-number">8.</span> <span class="nav-text">小结</span></a></li></ol></div>
            

          </div>
        </section>
      <!--/noindex-->
      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; 2018 &mdash; <span itemprop="copyrightYear">2019</span>
  <span class="with-love" id="animate">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">meixiaoliang</span>

  

  
</div>




  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动 v3.7.1</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/theme-next/hexo-theme-next">NexT.Mist</a> v6.2.0</div>




        








        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>


























  
  
    <script type="text/javascript" src="/blog/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/blog/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  


  


  <script type="text/javascript" src="/blog/js/src/utils.js?v=6.2.0"></script>

  <script type="text/javascript" src="/blog/js/src/motion.js?v=6.2.0"></script>



  
  

  
  <script type="text/javascript" src="/blog/js/src/scrollspy.js?v=6.2.0"></script>
<script type="text/javascript" src="/blog/js/src/post-details.js?v=6.2.0"></script>



  


  <script type="text/javascript" src="/blog/js/src/bootstrap.js?v=6.2.0"></script>



  



	





  





  










  





  

  

  

  

  
  

  

  

  

  

  

</body>
</html>
